package threeSum;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Date 2020/03/27
 * @author 王光浩
 * @Thinking 使用双指针，建议去做一下two sum
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
public class MyMethodThree {
	 public List<List<Integer>> threeSum(int[] nums) {
		 List<List<Integer>> ret=new LinkedList<>();
		 Arrays.sort(nums);
		 for(int i=0;i<nums.length;i++) {
			 if(i>0 && nums[i]==nums[i-1])continue;
			 int target=-nums[i];
			 int first=i+1;
			 int last=nums.length-1;
			 while(first<last) {
				 if(nums[first]+nums[last]==target) {
					 List<Integer> curr=new LinkedList<Integer>();
					 curr.add(nums[i]);
					 curr.add(nums[first]);
					 curr.add(nums[last]);
					 ret.add(curr);
					 first++;last--;
					 while(first<nums.length && nums[first]==nums[first-1])first++;
					 while(last>=0 && nums[last]==nums[last+1])last--;
				 }
				 else if(nums[first]+nums[last]<target)
					 first++;
				 else 
					 last--;
			 }
		 }
		 return ret;
	 }
}
